{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 第1章-统计学习方法概论-泛化误差上界\n",
    "### 定理：泛化误差上界\n",
    "&emsp;&emsp;对于二分类问题，当假设空间是有限个函数的集合$F=\\left\\{f_{1}, f_{2}, \\cdots, f_{d}\\right\\}$时，对任意一个函数$f \\in F$，至少以概率$1-\\delta$，以下不等式成立：$$R(f) \\leq \\hat{R}(f)+\\varepsilon(d, N, \\delta)$$其中$\\displaystyle \\varepsilon(d, N, \\delta)=\\sqrt{\\frac{1}{2 N}\\left(\\log d+\\log \\frac{1}{\\delta}\\right)}$ \n",
    "\n",
    "### Hoeffding不等式\n",
    "&emsp;&emsp;有随机变量序列$x_1,x_2, \\cdots, x_n$，定义随机变量的和$S_n=x_1+x_2+ \\cdots + x_n$，随机变量和的期望为$ES_n=E(\\sum x_i)$，随机变量$x_i$能被一个区间控制住，记为$x_i \\in [a_i, b_i]$，满足上述这些条件，就会有如下不等式：$$\n",
    "P\\left(S_{n}-ES_{n} \\geqslant t\\right) \\leqslant \\exp \\left(-\\frac{2 t^{2}}{2\\left(b_{i}-a_{i}\\right)^{2}}\\right)$$这样的一个形式不太好理解，我们给该公式做一个变形。不考虑随机变量序列的和，而是考虑序列的均值$\\overline{x}_{n}$。 \n",
    "\n",
    "&emsp;&emsp;由上式可以得到：$\\displaystyle \\overline{x}_{n} = \\frac{S_n}{n}，E\\left(\\overline{x}_{n}\\right)=\\frac{E S_{n}}{n}$  \n",
    "\n",
    "&emsp;&emsp;现考虑随机变量序列的均值与均值期望之间的距离大于等于$t$的概率为$P\\left(\\overline{x}_{n}-E\\left(\\overline{x}_{n}\\right) \\geqslant t\\right)$  \n",
    "\n",
    "公式推导如下：$\\displaystyle P\\left(\\overline{x}_{n}-E\\left(\\overline{x}_{n}\\right) \\geqslant t\\right)=P(S_n-ES_n \\geqslant t) \\leqslant \\exp \\left(-\\frac{2 n^2 t^2}{\\sum (b_{i}-a_{i})^2}\\right)$，当$n$比较大的时候，该概率为$O(e^{-n})$，当$n \\rightarrow \\infty $时，概率趋近于0。  \n",
    "\n",
    "&emsp;&emsp;得$\\displaystyle P(\\overline{X}-E\\overline{X} \\geqslant t) \\leqslant \\exp \\left(-\\frac{2 n^2 t^2}{\\sum (b_{i}-a_{i})^2}\\right)$，该公式中期望和均值是可以交换的，更改为$\\displaystyle P(E\\overline{X}-\\overline{X} \\geqslant t) \\leqslant \\exp \\left(-\\frac{2 n^2 t^2}{\\sum (b_{i}-a_{i})^2}\\right)$  \n",
    "\n",
    "### 证明\n",
    "&emsp;&emsp;现考虑二分类问题，在该问题中，从假设空间中任取一个备选模型$f$，这个模型在训练集上的经验风险（即为随机变量的均值）$\\hat{R}(f)=\\frac{1}{N}\\sum L(x_i, f(x_i))$，期望风险（这个模型在测试集上的表现）为$R(f)$，将上述两个风险带入到Hoeffding不等式中，  \n",
    "得到$\\displaystyle P(R(f)-\\hat{R}(f) \\geqslant t) \\leqslant \\exp(-\\frac{2N^2t^2}{N}) = \\exp(-2Nt^2)$，以上是得到了一个备选模型成立的情况。但是在假设空间中有$d$个备选模型，并不知道会从这些备选模型中选取到哪一个，所以要求这些模型在训练集上的经验风险和期望风险的差值都不大，现考虑该条件的对立面：$$ P(\\exists f \\in F, R(f)- \\hat{R}(f) \\geqslant t) = P(\\bigcup_{f \\in F}\\{R(f) - \\hat{R}(f) \\geqslant t \\}) \\leqslant \\sum_{f \\in F}P(R(f) = \\hat{R}(f) \\geqslant t) \\leqslant d\\exp (-2Nt^2)$$  \n",
    "\n",
    "&emsp;&emsp;对于$P(\\forall f \\in F, R(f) - \\hat{R}(f) \\leqslant t) \\geqslant 1 - d \\exp (-2Nt^2)$，最后将$t$换成$\\varepsilon$，得到$\\delta = d \\exp (-2N \\varepsilon^2)$，变量交换得到$\\displaystyle \\varepsilon = \\sqrt{\\frac{1}{2N} \\left( \\log d + \\log \\frac{1}{\\delta} \\right)}$。  \n",
    "故至少以概率$1 - \\delta$有$R(f) \\leq \\hat{R}(f)+\\varepsilon(d, N, \\delta)$，其中$\\varepsilon由上式得出$，定理得证。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
